package normalArray;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;

public class merge {
    // 法一：双指针
    // start_i和end_i可能相等
    // 每个区间不一定满足单调关系
    public static int[][] merge(int[][] intervals) {
        if (intervals.length == 1) {
            return intervals;
        }
        // 考虑先去重
        // 可能出现连续合并的情况 16 23 45 78
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            };
            
        });
        int left = 0, right = 1;
        LinkedList<int[]> list = new LinkedList<>();
        
        for(int[] subArray: intervals){
            list.add(subArray);
        }
        
        int offset=0;
        while (right < list.size()) {
            // 17 23 45 78
            // 12 34 56
            // 14 34 56
            if (list.get(left)[1] < list.get(right)[0]) {
                left++;
                right++;
            } else if (list.get(left)[1] == list.get(right)[0]) {
                // 都是合并
                // 12 22 23 34
                // 12 24
                // 先合并后删除
                list.set(left, new int[]{list.get(left)[0],list.get(right)[1]});
                list.remove(right);
                // offset++;
            }else{
                if (list.get(left)[1]>=list.get(right)[1]) {
                    //14 23 34 45
                    list.remove(right);
                }else{
                    //14 25
                    list.set(left, new int[]{list.get(left)[0],list.get(right)[1]});
                    list.remove(right);
                }
            }
        }
        int [][] rs =new int[list.size()][2];
         
  
        return list.toArray(new int[list.size()][]);
    }
    // 法一的优化
    public static int[][] merge2(int[][] intervals){
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            };
        });
        ArrayList<int[]> list =new ArrayList<>(intervals.length);
        for(int[] sub:intervals){
            if (list.size()==0||list.get(list.size()-1)[1]<sub[0]) {
                list.add(sub);
            }else{
                //14 45
                int max = Math.max(list.get(list.size()-1)[1], sub[1]);
                sub[1]=max;
                sub[0]=list.get(list.size()-1)[0];
                list.set(list.size()-1, sub);

            }
        }
        return list.toArray(new int[list.size()][]);
    }

    public static void main(String[] args) {
        // int[][] intervals = new int[][] { { 1, 3 }, { 2, 6 }, { 8, 10 }, { 15, 18 } };
        // int[][] intervals = new int[][] { { 1, 4 }, { 4, 5 } };
        // int[][] intervals = new int[][] { { 1, 2 }, { 2, 2 },{2,2},{2,10},{3,7},{4,6} };
        int[][] intervals = new int[][] { { 1, 4 }, { 0, 4 }};
        int[][] rs = merge2(intervals);
        for (int i = 0; i < rs.length; i++) {
            System.out.println("==========");
            System.out.println(rs[i][0]+":"+rs[i][1]);
        }
        System.out.println(rs);
    }
}
